package com.primes.functions;

import java.util.ArrayList;
import java.util.TreeMap;
import java.util.TreeSet;


public class EulerTotient {

	static Long[] arr = null;

	public static ArrayList<Long> getFactors(long num, ArrayList<Long> factors) {

		for (int i = 1; i < arr.length && arr[i] <= num; i++) {
			if (num % arr[i] == 0) {
				factors.add(arr[i]);
				return getFactors(num / arr[i], factors);
			}
		}
		return factors;
	}

	public static TreeMap<Long,Long> eulerTotients(int n){
		arr=Prime.primes(n).values().toArray(new Long[0]);
		TreeMap<Long,Long> ret= new TreeMap<Long,Long>();
		ret.put(1L, 1L);
		for (long i = 2; i < n; i++) {
			ArrayList<Long> factors = new ArrayList<Long>();
			getFactors(i, factors);

			long fi = 1;
			long prev = 1;
			for (Long fact : factors) {
				if (prev != fact)
					fi *= (fact - 1); // (n-1)*(m-1)
				else
					fi *= fact; // n^x-n^(x-1)
				prev = fact;
			}
			ret.put(i, fi);
			
		}
		return ret;

	}
	
	
}
